package org.schat;

import java.util.Arrays;

/**
 * @Description
 * @Author lsh
 * @Date 2020/3/25 9:44
 **/
public class Coin {

    /**
     *题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，再给一个总金额 n，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，则回答 -1 。
     * 比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1
     */
    public static void main(String[] args){
        int[] coins = {1,2,5};
        int amount = 11;
        System.out.println(coinChangeRemenber(coins,amount));
        System.out.println(coinChanageFor(coins,amount));
    }


    //普通递归求解
    static int coinChange(int[] coins,int amount){
        if(amount == 0)return 0;
        int ans = Integer.MAX_VALUE;
        for(int coin: coins){
            //金额不可达
            if(amount - coin < 0)continue;
            int subProb = coinChange(coins,amount - coin);
            //子问题无解
            if(subProb == -1)continue;
            ans = Math.min(ans,subProb + 1);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    //带备忘录递归求解
    static int coinChangeRemenber(int[] coins,int amount){
        int[] memo = new int[amount +1];
        Arrays.fill(memo,-2);
        return coinChanageHelper(coins,amount,memo);
    }

    static int coinChanageHelper(int[] coins,int amount,int[] memo){
        if(amount == 0) return 0;
        //查找备忘录，如果有答案就直接返回
        if(memo[amount] != -2) return memo[amount];
        int ans = Integer.MAX_VALUE;
        for(int coin: coins){
            //金额不可达
            if(amount - coin < 0)continue;
            int subProb = coinChanageHelper(coins,amount - coin,memo);
            //子问题无解
            if(subProb == -1)continue;
            ans = Math.min(ans,subProb + 1);
        }
        //记录当前金额的答案
        memo[amount] = ans == Integer.MAX_VALUE ? -1 : ans;
        return memo[amount];
    }

    static int coinChanageFor(int[] coins,int amount){
        //记录 0 - amount的每个amount 的最小解
        int[] dp = new int[amount +1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i = 0; i < dp.length; i++){
            for(int coin:coins){
                //判断当前金额是否有解
                if(i - coin < 0)continue;
                dp[i] = Math.min(dp[i],1+dp[i - coin]);
            }
        }
        return dp[amount] == (amount+1) ? -1 : dp[amount];

    }

}
